package strategies;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import stateInfo.Cell;
import stateInfo.CellProperty;
import stateInfo.GameState;
import utilities.HOF;

public class SimpleBFS {

	GameState gameState;

	public SimpleBFS(GameState gsIn) {
		gameState = gsIn;
	}

	
	public Cell simpleSearch(int maxDepth, Cell m, CellProperty targetType) {
		// Logger.log("beginning search from " + m.row + " " + m.col);
		List<Cell> frontier = new ArrayList<Cell>();
		frontier.add(m);
		Set<Cell> seen = new HashSet<Cell>();
		Map<Cell, Cell> predecessors = new HashMap<Cell, Cell>();
		Map<Cell, Integer> pathLengths = new HashMap<Cell, Integer>();
		pathLengths.put(m, 0);

		return simpleSearchRecursive(frontier, targetType, seen, maxDepth,
				new HOF.Function_1<Cell, Boolean>() {
					public Boolean apply(Cell m) {
						return (gameState.isWater(m) || gameState.isMyAnt(m));
					}

				}, predecessors, pathLengths);

	}

	public Cell simpleSearchRecursive(
			List<Cell> frontier, // sometimes called
									// "open"
			CellProperty targetType,
			Set<Cell> seen, // sometimes called "closed"
			int maxDepth, HOF.Function_1<Cell, Boolean> isBlocked,
			Map<Cell, Cell> predecessors, Map<Cell, Integer> pathLengths) {

		if (frontier.isEmpty()) {
			// Logger.log("BFS terminated with no goal found ");
			return null;
		}

		Cell currNode = frontier.remove(0);
		if (pathLengths.get(currNode) > maxDepth)
			return null;

		// Logger.log("removed " + currNode.row + " " + currNode.col +
		// " from frontier");
		List<Cell> newFrontier = new ArrayList<Cell>();
		newFrontier.addAll(frontier);
		for (Cell m : gameState.getLandNeighbors(currNode))
			if (!(seen.contains(m))) {
				seen.add(m);
				predecessors.put(m, currNode);
				if (gameState.hasProperty(targetType, m)) {
					// Logger.log("found " + targetType.toString( ) + " at " +
					// m.row + " " + m.col);
					return m;

				} else if (!(isBlocked.apply(m))) {
					newFrontier.add(m);
					// Logger.log("adding " + m.row + " " + m.col +
					// " to frontier");

					pathLengths.put(m, pathLengths.get(currNode) + 1);
					// Logger.log("adding succ: " + m.row + " " + m.col +
					// " pred: " + currNode.row + " "
					// + currNode.col + " to predecessors");
				}
			} else if (pathLengths.containsKey(m)) {
				int length = pathLengths.get(m);
				int newLength = pathLengths.get(currNode) + 1;
				if (length > newLength) {
					pathLengths.remove(m);
					pathLengths.put(m, newLength);
				}
			}

		Set<Cell> newSeen = new HashSet<Cell>();
		newSeen.addAll(seen);
		newSeen.add(currNode);

		return simpleSearchRecursive(newFrontier, targetType, newSeen,
				maxDepth, new HOF.Function_1<Cell, Boolean>() {
					public Boolean apply(Cell m) {
						return (gameState.isWater(m) || gameState.isMyAnt(m));
					}

				}, predecessors, pathLengths);

	}

	public int countTargets(int maxDepth, Cell m, final CellProperty targetType) {
		// Logger.log("beginning count targets search from " + m.row + " " +
		// m.col);
		int count = 0;
		List<Cell> frontier = new ArrayList<Cell>();
		frontier.add(m);
		Set<Cell> seen = new HashSet<Cell>();
		Map<Cell, Cell> predecessors = new HashMap<Cell, Cell>();
		Map<Cell, Integer> pathLengths = new HashMap<Cell, Integer>();
		pathLengths.put(m, 0);
		return countTargetsRecursive(frontier, targetType, seen, maxDepth,
				new HOF.Function_1<Cell, Boolean>() {
					public Boolean apply(Cell m) {
						return (gameState.isWater(m) || gameState.hasProperty(
								targetType, m));
					}

				}, predecessors, pathLengths, count);

	}

	public int countTargetsRecursive(
			List<Cell> frontier, // sometimes called
									// "open"
			CellProperty targetType,
			Set<Cell> seen, // sometimes called "closed"
			int maxDepth, HOF.Function_1<Cell, Boolean> isBlocked,
			Map<Cell, Cell> predecessors, Map<Cell, Integer> pathLengths,
			int count) {
		// Logger.log("looking for targets of type " + targetType.toString( ) +
		// " max depth: " + maxDepth);

		if (frontier.isEmpty()) {
			// Logger.log("empty frontier");
			return count;
		}

		Cell currNode = frontier.remove(0);
		if (pathLengths.get(currNode) > maxDepth)
			return count;
		// Logger.log("removed " + currNode.row + " " + currNode.col +
		// " from frontier");
		List<Cell> newFrontier = new ArrayList<Cell>();
		newFrontier.addAll(frontier);
		for (Cell m : gameState.getLandNeighbors(currNode)) {

			if (!(seen.contains(m))) {
				seen.add(m);
				predecessors.put(m, currNode);

				// Logger.log(m.row + " " + m.col + ": " + targetType.toString(
				// ) + "? " + gameState.hasProperty(targetType, m));

				if (gameState.hasProperty(targetType, m)) {
					// Logger.log("found " + targetType.toString( ) + " at " +
					// m.row + " " + m.col);
					count += 1;

				} else if (!(isBlocked.apply(m))) {
					newFrontier.add(m);
					// Logger.log("adding " + m.row + " " + m.col +
					// " to frontier");

					pathLengths.put(m, pathLengths.get(currNode) + 1);
					// Logger.log("adding succ: " + m.row + " " + m.col +
					// " pred: " + currNode.row + " "
					// + currNode.col + " to predecessors");
				}
			} else if (pathLengths.containsKey(m)) {
				int length = pathLengths.get(m);
				int newLength = pathLengths.get(currNode) + 1;
				if (length > newLength) {
					pathLengths.remove(m);
					pathLengths.put(m, newLength);
				}
			}
			// Logger.log(m.row + " " + m.col + " depth: " +
			// pathLengths.get(m));

		}

		Set<Cell> newSeen = new HashSet<Cell>();
		newSeen.addAll(seen);
		newSeen.add(currNode);

		return countTargetsRecursive(newFrontier, targetType, newSeen,
				maxDepth, new HOF.Function_1<Cell, Boolean>() {
					public Boolean apply(Cell m) {
						return (gameState.isWater(m) || gameState.isMyAnt(m));
					}

				}, predecessors, pathLengths, count);

	}

	public int distanceToNearestTarget(int maxDepth, Cell m, final CellProperty targetType) {
		List<Cell> frontier = new ArrayList<Cell>();
		frontier.add(m);
		Set<Cell> seen = new HashSet<Cell>();
		Map<Cell, Cell> predecessors = new HashMap<Cell, Cell>();
		Map<Cell, Integer> pathLengths = new HashMap<Cell, Integer>();
		pathLengths.put(m, 0);
		return distanceToNearestTargetRecursive(frontier, targetType, seen, maxDepth,
				new HOF.Function_1<Cell, Boolean>() {
					public Boolean apply(Cell m) {
						return (gameState.isWater(m) || gameState.hasProperty(
								targetType, m));
					}

				}, predecessors, pathLengths);

	}

	public int distanceToNearestTargetRecursive(
			List<Cell> frontier, // sometimes called
									// "open"
			CellProperty targetType,
			Set<Cell> seen, // sometimes called "closed"
			int maxDepth, HOF.Function_1<Cell, Boolean> isBlocked,
			Map<Cell, Cell> predecessors, Map<Cell, Integer> pathLengths) {
		// Logger.log("looking for targets of type " + targetType.toString( ) +
		// " max depth: " + maxDepth);

		if (frontier.isEmpty()) {
			// Logger.log("empty frontier");
			return 1000;
		}

		Cell currNode = frontier.remove(0);
		if (pathLengths.get(currNode) > maxDepth)
			return 1000;
		// Logger.log("removed " + currNode.row + " " + currNode.col +
		// " from frontier");
		List<Cell> newFrontier = new ArrayList<Cell>();
		newFrontier.addAll(frontier);
		for (Cell m : gameState.getLandNeighbors(currNode)) {

			if (!(seen.contains(m))) {
				seen.add(m);
				predecessors.put(m, currNode);

				if (gameState.hasProperty(targetType, m)) {
					return pathLengths.get(currNode) +1;

				} else if (!(isBlocked.apply(m))) {
					newFrontier.add(m);
					pathLengths.put(m, pathLengths.get(currNode) + 1);
				} 
			}

		}

		Set<Cell> newSeen = new HashSet<Cell>();
		newSeen.addAll(seen);
		newSeen.add(currNode);

		return distanceToNearestTargetRecursive(newFrontier, targetType, newSeen,
				maxDepth, new HOF.Function_1<Cell, Boolean>() {
					public Boolean apply(Cell m) {
						return (gameState.isWater(m) || gameState.isMyAnt(m));
					}

				}, predecessors, pathLengths);

	}

}
